package com.bupt.sort;

public class Sort {
	/**
	 * 交换数组中的两个元素
	 * 
	 * @param arr
	 * @param i
	 * @param j
	 */
	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
			
		arr[i] = arr[j];
		arr[j] = temp;
	}

	/**
	 * 直接冒泡排序
	 * 
	 * @param arr
	 */
	public static int[] bubbleSort1(int[] arr) {
		int i, j, len;
		len = arr.length;
		for (i = 0; i < len; i++) {
			for (j = 1; j < len - i; j++) {
				if (arr[j - 1] > arr[j]) {
					swap(arr, j, j - 1);
				}
			}
		}
		return arr;
	}

	/**
	 * 冒泡排序2，改进：如果又一轮没有进行交换，说明排序过程已经完成
	 * 
	 * @param arr
	 * @return
	 */
	public static int[] bubbleSort2(int[] arr) {
		boolean flag = true;
		int j, k, len;
		len = arr.length;
		k = len;
		while (flag) {
			flag = false;
			for (j = 1; j < k; j++) {
				if (arr[j - 1] > arr[j]) {
					swap(arr, j - 1, j);
					flag = true;
				}
			}
			k--;
		}
		return arr;
	}

	/**
	 * 冒泡排序3，设置flag标志，
	 * 
	 * @param arr
	 * @return
	 */
	public static int[] bubbleSort3(int[] arr) {
		int i, k, flag, len;
		len = arr.length;
		flag = len;
		while (flag > 0) {
			k = flag;
			flag = 0;
			for (i = 1; i < k; i++) {
				if (arr[i - 1] > arr[i]) {
					swap(arr, i - 1, i);
					flag = i;
				}
			}
		}
		return arr;
	}
	/**
	 * 插入排序1
	 * @param arr
	 * @return
	 */
	public static int[] simpleInsertSort(int[] arr) {
		int i, j,temp, len;
		len = arr.length;
		for(i = 1;i<len;i++){
			if(arr[i] < arr[i-1]){
				temp = arr[i];
				for(j=i-1;j>=0&&arr[j]>temp;j--){
					arr[j+1] = arr[j];
				}
				arr[j+1] = temp;
			}
		}
		return arr;
	}
	/**
	 * 从i节点向下调整大顶堆
	 * @param arr
	 * @param i
	 * @param n
	 */
	public void maxHeapFixDown(int[] arr,int i,int n){
		int j = i*2 + 1 , temp = arr[i];
		while( j <= n){
			if( j+1 <= n && arr[j+1] >= arr[j] ) j++;
			if( temp >= arr[j])  break;
			arr[i] = arr[j];
			i = j;
			j = i*2 + 1;
		}
		arr[i] = temp;
	}
	/**
	 * 建造大顶堆
	 * @param arr
	 */
	public void maxHeapBuild(int[] arr){
		for(int i = (arr.length-2)/2; i>=0 ; i--){
			maxHeapFixDown(arr, i, arr.length-1);
		}
	}
	/**
	 * 堆排序
	 * @param arr
	 * @return
	 */
	public int[] heapSort(int[] arr){
		maxHeapBuild(arr);
		for(int i = arr.length-1;i>0;i--){
			int temp = arr[i];
			arr[i] = arr[0];
			arr[0] = temp;
			maxHeapFixDown(arr, 0, i-1);
		}
		return arr;
	}
	/**
	 * 归并排序
	 * @param arr
	 * @return
	 */
	public int[] mergeSort(int[] arr){
		int[] tempArr = new int[arr.length];
		mergeSortArr(arr, 0, arr.length-1, tempArr);
		tempArr = null;
		return arr;
	}
	
	public void mergeSortArr(int[] arr,int left,int right,int[] tempArr){
		if(left < right){
			int mid = (left + right)/2;
			mergeSortArr(arr,left,mid,tempArr);
			mergeSortArr(arr,mid+1,right,tempArr);
			mergeArray(arr, left, mid+1, right, tempArr);
		}
	}
	public void mergeArray(int[] arr,int left,int mid,int right,int[] tempArr){
		int i = left, j = mid, m = left;
		while( i< mid && j <= right){
			if(arr[i] <= arr[j]){
				tempArr[m++] = arr[i++];
			}else{
				tempArr[m++] = arr[j++];
			}
		}
		if(i >= mid){
			for(int k = j;k <= right;k++){
				tempArr[m++] = arr[k];
			}
		}
		if(j > right){
			for(int k = i;k < mid;k++){
				tempArr[m++] = arr[k];
			}
		}
		for(int k = left; k<= right;k++ ){
			arr[k] = tempArr[k];
		}
	}
}
